Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Count Good Nodes in Binary Tree

Problem Statement

Given a binary tree root, return the number of good nodes in the binary tree.

A node is considered good if in the path from the root to this node, there are no nodes with a value greater than this node's value.

Examples

Example 1

  • Input: root = [3, 1, 3, 3, null, 1, 5]
Image
  • Expected Output: 4
  • Explanation:
    • Root node (3) is always good.
    • Node 5 is also a good node.
    • Both nodes 3 are good.

Example 2

  • Input: root = [2, 3, 4, 1, null, null, 5]
Image
  • Expected Output: 4
  • Explanation:
    • Nodes 2, 3, 4, and 5 are good.
    • The node with value 1 is not good because 3 is greater and comes before it.

Example 3

  • Input: root = [10, 8, 15, 7, 9, 12, 20]
Image
  • Expected Output: 3
  • Explanation:
    • Nodes 10, 15, and 20 are good.

Constraints:

  • The number of nodes in the binary tree is in the range [1, 10^5].
  • Each node's value is between [-104, 10^4].

Solution

To solve this problem, we will use Depth-First Search (DFS) traversal. The idea is to traverse the tree starting from the root and keep track of the maximum value encountered on the path from the root to the current node. If the current node's value is greater than or equal to the maximum value seen so far, it is a good node. We then update the maximum value and continue to traverse the tree.

This approach works because it ensures that we only count a node as good if all nodes on the path from the root to that node have values less than or equal to the current node's value. By updating the maximum value dynamically as we traverse, we can efficiently determine if a node is good.

Step-by-step Algorithm

  1. Initialization:

    • Start with the root node of the tree.
  2. Define Helper Function (DFS):

    • Define a helper function dfs(node, maxVal) to perform depth-first search (DFS) on the tree. Initially, consider root node's value as a maxVal.
    • If the current node is null, return 0 because there are no nodes to consider.
  3. Check Good Node:

    • Check if the value of the current node is greater than or equal to maxVal.
    • If it is, this node is a good node. Initialize a variable count to 1.
    • Otherwise, set count to 0.
  4. Update Maximum Value:

    • Update maxVal to be the maximum of the current node's value and the previous maxVal.
  5. Recur for Subtrees:

    • Recursively call dfs for the left child of the current node with the updated maxVal and add the result to count.
    • Recursively call dfs for the right child of the current node with the updated maxVal and add the result to count.
  6. Return Count:

    • Return the total count of good nodes found in the current subtree.

Algorithm Walkthrough

Image
  1. Initialization:

    • Start at the root node with value 2.
    • Initialize maxVal = 2.
  2. Step-by-Step DFS Traversal:

    • At Node 2:

      • maxVal = 2
      • 2 >= 2, so node 2 is a good node.
      • Count = 1
      • Update maxVal = max(2, 2) = 2
      • Recur for left child (Node 3).
    • At Node 3:

      • maxVal = 2
      • 3 >= 2, so node 3 is a good node.
      • Count = 1
      • Update maxVal = max(2, 3) = 3
      • Recur for left child (Node 1).
    • At Node 1:

      • maxVal = 3

      • 1 < 3, so node 1 is not a good node.

      • Count = 0

      • maxVal remains 3

      • Recur for left and right children (both are null), so return 0 for both.

      • Total count from Node 1's subtree: 0

    • Back at Node 3:

      • Count from left subtree (Node 1) = 0
      • Recur for right child (null), so return 0.
      • Total count from Node 3's subtree: 1 (Node 3 itself)
    • Back at Node 2:

      • Count from left subtree (Node 3) = 1
      • Recur for right child (Node 4).
    • At Node 4:

      • maxVal = 2
      • 4 >= 2, so node 4 is a good node.
      • Count = 1
      • Update maxVal = max(2, 4) = 4
      • Recur for left child (null), so return 0.
      • Recur for right child (Node 5).
    • At Node 5:

      • maxVal = 4

      • 5 >= 4, so node 5 is a good node.

      • Count = 1

      • Update maxVal = max(4, 5) = 5

      • Recur for left and right children (both are null), so return 0 for both.

      • Total count from Node 5's subtree: 1

    • Back at Node 4:

      • Count from right subtree (Node 5) = 1
      • Total count from Node 4's subtree: 2 (Nodes 4 and 5)
    • Back at Node 2:

      • Count from right subtree (Node 4) = 2
      • Total count from Node 2's subtree: 4 (Nodes 2, 3, 4, 5)
  3. Final Count:

    • The total count of good nodes in the tree is 4.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of this algorithm is , where N is the number of nodes in the tree. This is because we visit each node exactly once during the DFS traversal.

Space Complexity

The space complexity is , where H is the height of the tree. This is due to the recursion stack used during the DFS traversal. In the worst case (for a skewed tree), H can be as large as N, leading to a space complexity of . For a balanced tree, the space complexity would be .

Count Good Nodes in Binary Tree (medium)
Path Sum III (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity